#ifndef DATA_STRUCTURE_HUFFMANTREE_H
#define DATA_STRUCTURE_HUFFMANTREE_H

#include <fstream>
#include "TreeNode.h"
#include "vector"
#include <cstring>
#include "map"

using namespace std;

class HuffmanTree {
private:
    vector<TreeNode *> *tree = new vector<TreeNode *>();//哈夫曼树
    map<char, string> *pw = new map<char, string>();//密码本

    /**
     * 递归创建密码本
     * @param idx 当前节点下标
     * @param code 当前节点编码
     * @return 子节点的键值对拼接字符串
     */
    string passwordRecursion(int idx, string code) {
        TreeNode *t = tree->at(idx);
        if (t->getData() == '\0') {//分支节点
            string str;
            str += passwordRecursion(t->getLch(), code + "0");
            str += passwordRecursion(t->getRch(), code + "1");
            return str;
        } else {//叶子节点
            string str;
            str += t->getData();
            str += ":" + code + "\n";
            pw->insert({t->getData(), code});
            return str;
        }
    }

public:

    /**
     * 创建树
     * @param inFileSrc 原文文件位置
     */
    void createTree(string inFileSrc) {
        //获取原文
        string fileStr = readFileTool(inFileSrc);

        //输入字符串录入树并加权
        map<char, TreeNode *> *nodeMap = new map<char, TreeNode *>();
        map<char, TreeNode *>::iterator iter;
        for (char i : fileStr) {
            iter = nodeMap->find(i);
            TreeNode *node;
            if (iter == nodeMap->end()) {//map里没找到则创建节点并添加进map
                node = new TreeNode(i);
                tree->push_back(node);
                nodeMap->insert({i, node});
            } else {//找到就加权值
                node = iter->second;
                node->addW();
            }
        }

        //开辟并填充分支节点
        int a = tree->size() - 1;
        for (int i = 0; i < a; ++i) {
            int min1 = -1, min2 = -1;
            //找权最小值和次小值节点下标
            for (int j = 0; j < tree->size(); ++j) {
                TreeNode *t = tree->at(j);
                if (t->getParent() == 0) {
                    //第一个下标初始化，如果后面out_of_range了说明循环没到2次
                    if (min1 == -1) {
                        //循环第一次
                        min1 = j;
                    } else if (min2 == -1) {
                        //循环第二次
                        if (tree->at(min1)->getWeight() > tree->at(j)->getWeight()) {
                            min2 = min1;
                            min1 = j;
                        } else {
                            min2 = j;
                        }
                    } else {
                        //循环2次以上
                        //找到最小值和次小值
                        if (t->getWeight() < tree->at(min1)->getWeight()) {
                            min2 = min1;
                            min1 = j;
                        } else if (t->getWeight() < tree->at(min2)->getWeight()) {
                            min2 = j;
                        }
                    }
                }
            }
            tree->at(min1)->setParent(a + i + 1);
            tree->at(min2)->setParent(a + i + 1);
            tree->push_back(new TreeNode(tree->at(min1)->getWeight() + tree->at(min2)->getWeight(), min1, min2));
        }
    }

    /**
     * cod文件压缩
     * @param inFile 需要压缩文件的位置
     * @param outFile 输出文件位置
     */
    static void compression(string inFile, string outFile) {
        string inStr = readFileTool(inFile);
        unsigned char c = 0;
        string outStr;
        //第一个字符存最后一个字节的实际长度
        outStr += (unsigned char) inStr.length() % 8;
        for (int i = 0; i < inStr.length(); ++i) {
            //按位或拼接每个字符
            c |= (inStr[i] - '0') << (7 - i % 8);
            if (i % 8 == 7 || i == inStr.length() - 1) {
                //把每个字符添加到字符串
                outStr += c;
                c = 0;
            }
        }
        writeFileBinaryTool(outFile, outStr);
    }

    /**
     * 解压并解码文件
     * @param inFile 需要解压文件的位置
     * @param outFile 输出文件的位置
     */
    void decompression(string inFile, string outFile) {
        string inStr = readFileBinaryTool(inFile);
        string outStr;
        //从第二个字符遍历
        for (int i = 1; i < inStr.length(); i++) {
            //需要处理的字符长度，最后一个字符如果不完整则遍历次数等于第一个字符的值
            int x = i == inStr.length() - 1 && inStr[0] > 0 ? inStr[0] : 8;
            for (int j = 0; j < x; j++) {
                //按位提取每位
                outStr += (unsigned char) ((inStr[i] & (1 << (7 - j))) >> (7 - j)) + 48;
            }
        }
//        writeFileTool(outFile,outStr);
        decodeS2F(outStr, outFile);
    }

    /**
     * 创建密码本
     * @param outFileSrc 密码本输出位置
     */
    void createCodeBook(string outFileSrc) {
        if (tree->size() > 1) {
            writeFileTool(outFileSrc, passwordRecursion(tree->size() - 1, ""));
        } else {
            //针对全文只有一种字符的情况
            writeFileTool(outFileSrc, passwordRecursion(tree->size() - 1, "0"));
        }
    }

    /**
     * 通过密码本对文件编码
     * @param inFileSrc 输入文件
     * @param outFileSrc 输出文件
     */
    void encode(string inFileSrc, string outFileSrc) {
        string out;
        string str = readFileTool(inFileSrc);
        for (char &i : str) {
            out += (*pw)[i];
        }
        writeFileTool(outFileSrc, out);
    }

    /**
     * 解码文件
     * @param inFileSrc 输入文件
     * @param outFileSrc 输出文件
     */
    void decodeF2F(string inFileSrc, string outFileSrc) {
        decodeS2F(readFileTool(inFileSrc), outFileSrc);
    }

    /**
     * 解码文件
     * @param str 密码
     * @param outFileSrc 输出文件
     */
    void decodeS2F(string str, string outFileSrc) {
        TreeNode *t = tree->at(tree->size() - 1);
        string out;
        for (char &i : str) {
            //指针找节点
            if (i == '0') {
                t = tree->at(t->getLch());
            } else {
                t = tree->at(t->getRch());
            }
            //找到就输出并让指针归位
            if (t->getData() != '\0') {
                out += t->getData();
                t = tree->at(tree->size() - 1);
            }
        }
        writeFileTool(outFileSrc, out);
    }

    /**
     * 字符文件读文件工具函数
     * @param fileSrc 待读文件地址
     * @return 文件内容
     */
    static string readFileTool(string fileSrc) {
        ifstream ifs;
        ifs.open(fileSrc, ios::in);
        if (!ifs.is_open()) {
            cout << "文件打开失败" << endl;
            return "";
        }
        string fileLine;
        string fileStr;
        char b;
        while ((b = ifs.get()) != EOF) {
            fileStr += b;
        }
        ifs.close();
        return fileStr;
    }

    /**
     * 二进制方式读文件工具函数
     * @param fileSrc 待读文件地址
     * @return 文件内容
     */
    static string readFileBinaryTool(string fileSrc) {
        unsigned char c;
        string fileStr;
        ifstream file(fileSrc, ios::out | ios::binary);
        if (!file) {
            cout << "文件打开失败";
            return "";
        }
        while (file.read((char *) &c, sizeof(unsigned char))) {
            fileStr += c;
        }
        file.close();
        return fileStr;
    }

    /**
     * 字符文件写文件工具函数
     * @param fileSrc 待写文件地址
     * @param data 待写内容
     */
    static void writeFileTool(string fileSrc, string data) {
        ofstream ofs;
        ofs.open(fileSrc, ios::out);
        ofs << data;
        ofs.close();
    }

    /**
     * 二进制方式写文件工具函数
     * @param fileSrc 待写文件地址
     * @param data 待写内容
     */
    static void writeFileBinaryTool(string fileSrc, string data) {
        ofstream file(fileSrc, ios::out | ios::binary);
        for (char &i : data) {
            file.write((char *) &i, sizeof(unsigned char));
        }
        file.close();
    }

};

#endif //DATA_STRUCTURE_HUFFMANTREE_H
